package leetcode.d_1_99;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

// 复原IP地址 https://leetcode.cn/problems/restore-ip-addresses/
public class P93 {
    List<String> res;
    String str;
    public List<String> restoreIpAddresses(String s) {
        res = new LinkedList<>();
        str = s;
        LinkedList<String> subRes = new LinkedList<>();
        dfs(subRes, 0);
        return res;
    }

    public void dfs(LinkedList<String> subRes, int start) {
        if (subRes.size() == 4 && start == str.length()) {
            res.add(String.join(".", subRes));
            return;
        }
        if (subRes.size() == 4 && start < str.length()) {
            return;
        }
        for (int length=1; length<=3; length++) {
            String temp = "";
            if (start+length-1 >= str.length()) {
                return;
            }
            if (length != 1 && str.charAt(start) == '0') {
                return;
            }
            temp = str.substring(start, start+length);
            if (Integer.valueOf(temp) > 255) {
                return;
            }
            subRes.add(temp);
            dfs(subRes, start+length);
            subRes.removeLast();
        }
    }

    public static void main(String[] args) {
        P93 test = new P93();
        String s = "25525511135";
        System.out.println(test.restoreIpAddresses(s).toString());
    }
}
